This description relates to matching patterns in digital data.
The widespread use of Internet applications coupled with the availability of system viruses and other malicious software has led to the growing need for network security. In some applications, firewalls and dedicated intrusion detection/prevention systems (IDS/IPS) are used to perform deep packet inspection to provide protection from network attacks. Some IDSs, for example, operate by first checking packet headers for certain types of attacks, then classifying the network packets, and subsequently performing pattern matching on packet payload against a known database of patterns.
Some approaches to pattern matching first transform a database of fixed strings/regular expressions into an abstract machine, such as a nondeterministic finite automaton (NFA) or a deterministic finite automaton (DFA). In some examples, a representation of the resulting abstract machine is stored in a memory and interpreted by application-specific hardware, which reads the input characters and detects the patterns in the database.
Integrating hardware accelerators in IDSs can be useful in improving the speed and efficiency of pattern matching. For large pattern databases, however, constructing a DFA can sometimes impose a memory penalty too great for building such an accelerator. An NFA may have a smaller memory requirement, but it may not be suitable for high-speed hardware implementations due to the non-deterministic nature of transitions and back-tracking on the data that is constructed by traditional approaches.